#include <stdio.h>
#include <stdlib.h>

// 定义求最大值的宏
#define max(a,b) ((a) > (b) ? (a) : (b))

int main() {
    int n, bagWeight;
    scanf("%d %d", &n, &bagWeight);

    // step 1# 申请存放物品重量和价值的数组
    int *weight = (int *)malloc(sizeof(int) * n);
    int *value = (int *)malloc(sizeof(int) * n);

    // step 2# 读入每个物品的重量和价值
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &weight[i], &value[i]);
    }

    // step 3# 定义二维dp数组，初始化为0
    int **dp = (int **)malloc(sizeof(int *) * n);
    for (int i = 0; i < n; i++) {
        dp[i] = (int *)malloc(sizeof(int) * (bagWeight + 1));
        for (int j = 0; j <= bagWeight; j++) {
            dp[i][j] = 0;
        }
    }

    // step 4# 初始化第一个物品
    for (int j = weight[0]; j <= bagWeight; j++) {
        dp[0][j] = dp[0][j - weight[0]] + value[0];
    }

    // step 5# 状态转移：遍历每个物品
    for (int i = 1; i < n; i++) { // 遍历物品
        for (int j = 0; j <= bagWeight; j++) { // 遍历背包容量
            if (j < weight[i]) {
                // step 5.1# 如果当前物品太重，装不进去，继承上一行的状态
                dp[i][j] = dp[i - 1][j];
            } else {
                // step 5.2# 可以选择：不装，或继续装同一个物品
                dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
            }
        }
    }

    // step 6# 输出最终结果
    printf("%d\n", dp[n - 1][bagWeight]);

    // step 7# 释放内存
    for (int i = 0; i < n; i++) {
        free(dp[i]);
    }
    free(dp);
    free(weight);
    free(value);

    return 0;
}
